// 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

// 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<bits/stdc++.h>
using namespace std;

// 记录+两次遍历

// 执行用时：
// 4 ms
// , 在所有 C++ 提交中击败了
// 73.92%
// 的用户
// 内存消耗：
// 10.2 MB
// , 在所有 C++ 提交中击败了
// 82.95%
// 的用户



 struct ListNode {
     int val;
     ListNode *next;
     ListNode(int x) : val(x), next(NULL) {}
 };

class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* cur = head;
        int cnt=0;
        while(cur!=nullptr){
            cur= cur->next;
            ++cnt;
        }
        cnt = cnt-k;
        cur = head;
        while(cnt>0){
            cur = cur->next;
            --cnt;
        }
        return cur;
    }
};